%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% This file is part of the book
%%
%% Algorithmic Graph Theory
%% http://code.google.com/p/graphbook/
%%
%% Copyright (C) 2009--2012 Minh Van Nguyen <mvngu.name@gmail.com>
%%
%% See the file COPYING for copying conditions.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\DontPrintSemicolon
\SetAlgoNoLine
%%
%% input
\KwIn{Three vertices $x,y,z$ of an augmented AVL tree $T_v$, where
  $z$ is the first height-unbalanced vertex in the path from $v$ up to
  the root of $T_v$. The left subtree of $z$ is $T_0$ and the right
  subtree of $y$ is $T_3$. The roots of the left and right subtrees of
  $x$ are denoted $T_1$ and $T_2$, respectively.}
%%
%% output
\KwOut{A right-left double rotation to height-balance the subtree
  rooted at $z$.}
\BlankLine
%%
%% algorithm body
$\rightChild[\parent[z]] \assign x$\;
$\parent[x] \assign \parent[z]$\;
$\parent[z] \assign x$\;
$\leftChild[x] \assign z$\;
$\rightChild[x] \assign y$\;
$\rightChild[z] \assign \rootElem[T_1]$\;
$\parent[\rootElem[T_1]] \assign z$\;
$\parent[y] \assign x$\;
$\leftChild[y] \assign \rootElem[T_2]$\;
$\parent[\rootElem[T_2]] \assign y$\;
$\height[z] \assign 1 + \max(\height[\rootElem[T_0]],\, \height[\rootElem[T_1]])$\;
$\height[y] \assign 1 + \max(\height[\rootElem[T_2]],\, \height[\rootElem[T_3]])$\;
$\height[x] \assign 1 + \max(\height[y],\, \height[z])$\;
